#include "headfiles.h"

using namespace std;

// Given an input A of integers, find the maximum of j-i 
// subjected to the constraint of A[i] < A[j].
int maxDistance(std::vector<int> input, int &start, int &end) {
    if (input.empty()) {
        return 0;
    }

    // Find the start point
    int i, min_val;
    vector<int> start_points_loc;
    
    min_val = input[0];
    size_t input_size = input.size();

    start_points_loc.push_back(0);
    for (i = 1; i < input_size; i++) {
        if (input[i] < min_val) {
            min_val = input[i];
            start_points_loc.push_back(i);
        }
    }

    // Scan from the last points to compare to
    // each start point
    vector<int>::reverse_iterator rit;
    int max_dist = 0;
    int max_start, max_end;
    for (i = input_size - 1; i >= 0; i--) {
        for (rit = start_points_loc.rbegin(); rit != start_points_loc.rend(); rit++) {
            if (input[i] > input[*rit]) {
                if (i - *rit > max_dist) {
                    max_start = *rit;
                    max_end = i;
                    max_dist = i - *rit;
                }
            }
        }
    }

    start_points_loc.clear();

    start = max_start;
    end = max_end;

    return max_dist;
}
